package org.example;

import java.util.Scanner;

public class Test3 {
    //完全背包 https://kamacoder.com/problempage.php?pid=1052
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt(),n = sc.nextInt();
        int[] w = new int[m], v = new int[m];
        for (int i = 0; i < m; i++) {
            w[i] = sc.nextInt();
            v[i] = sc.nextInt();
        }
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                dp[i][j] = dp[i-1][j];
                if (j >= w[i-1]) {
                    dp[i][j] = Math.max(dp[i][j],dp[i][j-w[i-1]] + v[i-1]);
                }
            }
        }
        System.out.println(dp[m][n]);
    }

    //优化

    /**
     * 完全背包和01背包的优化不同，因为01背包需要用到dp[i-1][j]和dp[i-1][j-w[i-1]]，首先填表的顺序是从上到下
     * 其次就是从右向左，因为一维数组中的数据就是dp[i-1]时候填表的顺序，优化之后需要用到的数据就是dp[j]和dp[j-w[i-1]]
     * 需要用到dp[j-w[i-1]]的数据，所以需要从右向左遍历
     * 而完全背包需要用到的数据就是dp[i-1][j]和dp[i][j-w[i-1]]，优化为一维数组之后就需要用到i-1填的数据以及本次
     * 循环i j次之前的数据，所以需要从左享向右遍历
     * @param args
     */
    public static void main1(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt(),n = sc.nextInt();
        int[] w = new int[m], v = new int[m];
        for (int i = 0; i < m; i++) {
            w[i] = sc.nextInt();
            v[i] = sc.nextInt();
        }
        int[] dp = new int[n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = w[i-1]; j <= n; j++) {
                dp[j] = Math.max(dp[j],dp[j-w[i-1]] + v[i-1]);
            }
        }
        System.out.println(dp[n]);
    }
}
